package merisis.util;

import java.util.Arrays;

public class SortedArraySetUtil {

	public static long[] add(long[] src, long element) {

		long[] r;

		if (src == null) {

			r = new long[1];
			r[0] = element;
			return r;
		}

		int srclen = src.length;

		// the point of insertion
		int ipt = Arrays.binarySearch(src, element);
		if (ipt >= 0) {
			// no insertion, because of the existence of a
			return src;
		}

		ipt = -ipt - 1;
		r = new long[srclen + 1];

		if (ipt == 0) {
			r[0] = element;
			System.arraycopy(src, 0, r, 1, srclen);
			return r;
		}

		if (ipt == srclen) {
			r[srclen] = element;
			System.arraycopy(src, 0, r, 0, srclen);
			return r;
		}

		System.arraycopy(src, 0, r, 0, ipt);
		r[ipt] = element;
		System.arraycopy(src, ipt, r, ipt + 1, srclen - ipt);

		return r;
	}

	public static long[] or(long[] a, long[] b) {

		long[] s0;
		long[] s1;

		if (a != null && b != null && a.length > b.length) {

			s0 = a;
			s1 = b;
		} else {

			s0 = b;
			s1 = a;
		}

		long[] s = s0;
		if (s1 != null) {
			for (int i = 0; i < s1.length; i++) {
				s = add(s, s1[i]);
			}
		}

		return s;
	}

	public static long[] andNot(long[] a, long[] b) {

		int[] indexOfHole = new int[b.length];
		int[] spanOfHole = new int[b.length];

		int m = 0;
		int n = a.length;
		int i = 0;
		int idx = 0;
		while (i < b.length) {

			long key = b[i];

			idx = Arrays.binarySearch(a, key);
			if (idx < 0) {
				i++;
				continue;
			}

			indexOfHole[m] = idx;
			int span = 1;

			i++;
			idx++;

			while (i < b.length && a[idx] == b[i]) {
				
				span++;
				i++;
				idx++;
			}

			spanOfHole[m] = span;
			n -= span;
			m++;
		}

		if (m == 0)
			return a;

		i = 0;
		int idxOfDest = indexOfHole[0];
		while (i < m) {

			idx = indexOfHole[i];
			int len;
			if (i + 1 < m)
				len = indexOfHole[i + 1] - idx - spanOfHole[i];
			else
				len = a.length - idx - spanOfHole[i];

			System.arraycopy(a, idx + spanOfHole[i], a, idxOfDest, len);
			idxOfDest += len;
			i++;
			
		}

		long[] r = new long[n];
		System.arraycopy(a, 0, r, 0, n);

		return r;
	}
}
